package Top_Interview_Questions.Tree;

import Top_Interview_Questions.Tree.Supple.Node;
import Top_Interview_Questions.Tree.Supple.TreeNode;

/**
 * @Author: 吕庆龙
 * @Date: 2020/2/10 11:15
 * <p>
 * https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/java-dfs-jian-zhi-9ms9244-by-lava-4/
 * 这题画图也没画明白为啥要这样写
 */
public class _0236 {

    public static void main(String[] args) {
        _0236 test = new _0236();

        TreeNode root = new TreeNode(3);
        TreeNode node1 = new TreeNode(5);
        TreeNode node2 = new TreeNode(1);
        TreeNode node3 = new TreeNode(6);
        TreeNode node4 = new TreeNode(2);
        TreeNode node5 = new TreeNode(0);
        TreeNode node6 = new TreeNode(8);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(4);

        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.left = node5;
        node2.right = node6;
        node4.left = node7;
        node4.right = node8;

        //这是结论3  参数: 3,5,1    3,6,2等
//        System.out.println(test.lowestCommonAncestor(root, node1, node2));
        //这是结论0 参数: 3,3,3
//        System.out.println(test.lowestCommonAncestor(root, root, root));
        //这是结论2,4的情况
        System.out.println(test.lowestCommonAncestor(root, node1, node3));
    }

    /**
     * 我们使用DFS搜索每一个节点的左右子树：
     * 1、若子树上存在p和q的公共节点，返回此公共节点
     * 2、若不存在公共节点，但是存在p或q任意一个节点，返回此节点
     * 3、若不存在公共、p、q节点，则返回null。
     *
     * 那么，有以下几个结论：
     * 0、若当前节点为null、p、q之一，直接返回当前节点
     * 1、若左子树上存在公共节点（返回值非p、q），则函数返回值为左子树返回值，不需再遍历右子树
     * 2、若左子树返回null，则函数返回值为右子树返回值
     * 3、若左子树、右子树返回值均为非null，则肯定为一个p，一个q，则公共节点为当前节点
     * 4、最后一种情况，即左子树返回非null，右子树返回null，则函数返回值为左子树返回值
     *
     * *针对p是q的子节点这种特殊情况，上述方案依然可行（但就没有办法剪枝了，可以考虑针对此情况加一个标记，
     * 不再遍历右子树）。
     *
     *              3
     *           /    \
     *          5      1
     *        /  \   /  \
     *       6   2  0    8
     *          / \
     *         7  4
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //结论0
        if (root == null || root == p || root == q)
            return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);

        //结论1
        if (left != null && left != q && left != p)
            return left;
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        //结论3
        if (left != null && right != null)
            return root;

            //结论2 4
        else
            return left == null ? right : left;
    }
}
